// 155. 最小栈

// 设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

// push(x) —— 将元素 x 推入栈中。
// pop() —— 删除栈顶的元素。
// top() —— 获取栈顶元素。
// getMin() —— 检索栈中的最小元素。
//

// 示例:
// 输入：
// ["MinStack","push","push","push","getMin","pop","top","getMin"]
// [[],[-2],[0],[-3],[],[],[],[]]

// 输出：
// [null,null,null,null,-3,null,0,-2]

// 解释：
// MinStack minStack = new MinStack();
// minStack.push(-2);
// minStack.push(0);
// minStack.push(-3);
// minStack.getMin();   --> 返回 -3.
// minStack.pop();
// minStack.top();      --> 返回 0.
// minStack.getMin();   --> 返回 -2.
//

// 提示：
// pop、top 和 getMin 操作总是在 非空栈 上调用。

/**
 * initialize your data structure here.
 */
var MinStack = function () {
  this.cur = [];
  this.min = [Infinity];
};

/**
 * @param {number} x
 * @return {void}
 */
MinStack.prototype.push = function (x) {
  this.cur.push(x);
  this.min.push(Math.min(x, this.min[this.min.length - 1]));
};

/**
 * @return {void}
 */
MinStack.prototype.pop = function () {
  this.min.pop();
  return this.cur.pop();
};

/**
 * @return {number}
 */
MinStack.prototype.top = function () {
  return this.cur[this.cur.length - 1];
};

/**
 * @return {number}
 */
MinStack.prototype.getMin = function () {
  return this.min[this.min.length - 1];
};

/**
 * @return {string}
 */
MinStack.prototype.toString = function () {
  return this.cur.toString();
};

/**
 * initialize your data structure here.
 */
var MinStack2 = function () {
  this.diff = [];
  this.min = -1;
};

/**
 * @param {number} x
 * @return {void}
 */
MinStack2.prototype.push = function (x) {
  if (this.diff.length == 0) {
    this.diff.push(0);
    this.min = x;
  } else {
    const d = x - this.min;
    this.diff.push(d);
    if (d < 0) {
      this.min = x;
    }
  }
};

/**
 * @return {void}
 */
MinStack2.prototype.pop = function () {
  if (this.diff.length > 0) {
    const d = this.diff.pop();
    if (d < 0) {
      const m = this.min;
      this.min -= d;
      return m;
    }
    return this.min + d;
  }
  return null;
};

/**
 * @return {number}
 */
MinStack2.prototype.top = function () {
  const d = this.diff[this.diff.length - 1];
  return d < 0 ? this.min : d + this.min;
};

/**
 * @return {number}
 */
MinStack2.prototype.getMin = function () {
  return this.min;
};

/**
 * @return {string}
 */
MinStack2.prototype.toString = function () {
  return this.diff.toString();
};

/**
 * Your MinStack object will be instantiated and called as such:
 * var obj = new MinStack()
 * obj.push(x)
 * obj.pop()
 * var param_3 = obj.top()
 * var param_4 = obj.getMin()
 */
const minStack = new MinStack2();
minStack.push(-2);
console.log(minStack.toString());
minStack.push(0);
console.log(minStack.toString());
minStack.push(-3);
console.log(minStack.toString());
console.log(minStack.getMin());
console.log(minStack.pop());
console.log(minStack.top());
console.log(minStack.getMin());
